package com.niuke;

import com.leetCode.tree.TreeNode;

import java.util.Stack;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-12-16 13:48:06
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-12-16     张李鑫                     1.0         1.0 Version
 */
public class JZ26 {
    /**
     * 输入两棵二叉树A，B，判断B是不是A的子结构。（我们约定空树不是任意一个树的子结构）
     * 假如给定A为{8,8,7,9,2,#,#,#,#,4,7}，B为{8,9,2}，2个树的结构如下，可以看出B是A的子结构
     */

    public static boolean HasSubtree(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null) {
            return false;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.add(root1);
        while (!stack.isEmpty()) {
            TreeNode pop1 = stack.pop();
            if (pop1.val == root2.val) {
                boolean equals = isEquals(pop1, root2);
                if (equals) {
                    return true;
                }
            }
            if (pop1.right != null) {
                stack.add(pop1.right);
            }
            if (pop1.left != null) {
                stack.add(pop1.left);
            }
        }
        return false;
    }

    public static boolean isEquals(TreeNode root1, TreeNode root2) {
        Stack<TreeNode> stack = new Stack<>();
        Stack<TreeNode> stack1 = new Stack<>();
        stack.add(root1);
        stack1.add(root2);
        while (!stack1.isEmpty() && !stack.isEmpty() && stack1.peek().val == stack.peek().val) {
            TreeNode pop = stack.pop();
            TreeNode pop1 = stack1.pop();

//
//            if (pop.right != null) {
//                stack.add(pop.right);
//            }
            if (pop1.right != null) {
                if (pop.right==null){
                    return false;
                }
                stack1.add(pop1.right);
                stack.add(pop.right);
            }

            if (pop1.left != null) {
                if (pop.left==null){
                    return false;
                }
                stack.add(pop.left);
                stack1.add(pop1.left);
            }
//            if (pop.left != null) {
//                stack.add(pop.left);
//            }
        }
        return stack1.size() == 0;
    }


    public static void main(String[] args) {
//        TreeNode treeNode = new TreeNode(8);
//        TreeNode treeNode1 = new TreeNode(8);
//        TreeNode treeNode2 = new TreeNode(7);
//        TreeNode treeNode3 = new TreeNode(9);
//        TreeNode treeNode4 = new TreeNode(2);
//        TreeNode treeNode5 = new TreeNode(4);
//        TreeNode treeNode6 = new TreeNode(7);
//
//        treeNode.left = treeNode1;
//        treeNode.right = treeNode2;
//
//        treeNode1.left = treeNode3;
//        treeNode1.right = treeNode4;
//
//        treeNode4.left = treeNode5;
//        treeNode4.right = treeNode6;

        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);


        treeNode1.left = treeNode2;
        treeNode1.right = treeNode3;
        treeNode2.left = treeNode4;
        treeNode2.right = treeNode5;




        TreeNode treeNode11 = new TreeNode(2);
        TreeNode treeNode12 = new TreeNode(3);
//        TreeNode treeNode13 = new TreeNode(3);


        treeNode11.left = treeNode12;
//        treeNode11.right = treeNode13;

        System.out.println(HasSubtree(treeNode1, treeNode11));
    }
}
